package org.example;
class Solution {
    //使用单调栈来解决,
    public static String removeKdigits(String num, int k) {
        if(num.length() == k) return "0";
        //利用StringBuilder作为栈容器,维护单调递增栈
        StringBuilder stack = new StringBuilder();
        for (char c : num.toCharArray()) {
            //当栈顶元素 > 当前字符,并且还能进行删除(k>0),弹出栈顶
            while(k > 0 && stack.length() > 0 && c < stack.charAt(stack.length() - 1)){
                stack.deleteCharAt(stack.length() - 1);
                k--;
            }
            //栈为空或者当前元素 >= 栈顶元素,加入栈
            stack.append(c);
        }

        //如果遍历完还有剩余k,直接从尾部删除最后k个字符
        //比如原数字本身就是严格递增序列时
        if(k > 0){
            stack.delete(stack.length() - k, stack.length());
        }
        //处理前导0,若最后删除为空,需要保留一个0返回
        String ret = stack.toString().replaceFirst("^0+", "");
        return ret.isEmpty() ? "0" : ret;
    }
}